Interpolating filter banks are presently used to process sampled signals in a wide variety of applications, such as video signal processing. A signal put through an interpolating filter bank may be in the form of a multidimensional lattice of sample points. For example, in video applications, an input signal put through the filter bank may be a three-dimensional set of pixels. The interpolating filter bank generally downsamples the input signal, thereby selecting a subset of the signal sample points for further processing. The filter bank includes predict filters for providing an estimate of the sample points which were removed as a result of the downsampling. The output of the predict filters may be supplied to other signal processing hardware or software for further processing of the downsampled signal. When this further processing is complete, the filter bank interpolates and upsamples the result to provide an output with the same number of sample points as the original input signal. The interpolating filter bank thus allows a high-resolution sampled signal to be processed at a lower sample rate, and then reconstructs the result to return the processed signal to its original resolution. Such filter banks are useful in numerous digital signal processing applications.
It is generally desirable for a filter bank to provide "perfect reconstruction." That is, a filter bank configured to downsample, interpolate, and then upsample a given input signal, without any further processing of the downsampled and interpolated signal, should ideally provide perfect reconstruction of the original input signal. Filter banks designed to provide this property are described in, for example, F. Mintzer, "Filters for distortion-free two-band multirate filter banks," IEEE Trans. Acoust. Speech Signal Process., Vol. 33, pp. 626-630, 1985; M. J. T. Smith and T. P. Barnwell, "Exact reconstruction techniques for tree-structured subband coders," IEEE Trans. Acoust. Speech Signal Process., Vol.34, No. 3, pp. 434-441, 1986; P. P. Vaidyanathan, "Theory and design of M-channel maximally decimated quadrature mirror filters with arbitrary M, having perfect reconstruction property," IEEE Trans. Acoust. Speech Signal Process., Vol. 35, No. 2, pp. 476-492, 1987; M. Vetterli, "Filter banks allowing perfect reconstruction," Signal Processing, Vol. 10, pp. 219-244, 1986.
The design of perfect reconstruction filter banks is related to the concept of "wavelets" in mathematical analysis. Wavelets have been defined as translates and dilates of a fixed function, and have been used to both analyze and represent general functions, as described in A. Grossman and J. Morlet, "Decomposition of Hardy functions into square integrable wavelets of constant shape," SIAM J. Math. Anal., Vol. 15, No. 4, pp. 723-736, 1984, and Y. Meyer, Ondelettes et Operateurs, I: Ondelettes, II: Operateurs de Calderon-Zygmund, III: (with R. Coifman), Operateurs multilineaires, Paris: Hermann, 1990, English translation of first volume, Wavelets and Operators, Cambridge University Press, 1993. In the late 1980s, the introduction of multiresolution analysis provided a connection between wavelets and the subband filters used in filter banks, as described in S. G. Mallat, "Multiresolution approximations and wavelet orthonormal bases of L.sup.2 (R)," Trans. Amer. Math. Soc., Vol. 315, No. 1, pp. 69-87, 1989. This led to the first construction of smooth, orthogonal, and compactly supported wavelets as described in I. Daubechies, "Orthonormal bases of compactly supported wavelets," Comm. Pure Appl. Math., Vol. 41, pp. 909-996, 1988. Many generalizations to biorthogonal or semiorthogonal wavelets followed. Biorthogonality allows the construction of symmetric wavelets and thus linear phase filters as described in A Cohen, I. Daubechies, and J. Feauveau, "Bi-orthogonal bases of compactly supported wavelets," Comm. Pure Appl. Math., Vol. 45, pp. 485-560, 1992; and M. Vetterli and C. Herley, "Wavelets and filter banks: Theory and design," IEEE Trans. Acoust. Speech Signal Process., Vol. 40, No. 9, pp. 2207-2232, 1992. For further background information on wavelets and subband filters, see, for example, I. Daubechies, "Ten Lectures on Wavelets," CBMS-NSF Regional Conf. Series in Appl. Math., Vol. 61, Philadelphia, Pa.: Society for Industrial and Applied Mathematics, 1992; M. Vetterli and J. Kovacevic, "Wavelets and Subband Coding," Prentice Hall, Englewood Cliffs, N.J., 1995; and G. Strang and T. Nguyen, "Wavelets and Filter Banks," Wellesley, Cambridge, 1996.
An important unsolved problem in filter bank design is how to generalize filter banks to process signals in multiple dimensions. One possible approach is to use tensor products of available one-dimensional solutions, which generally leads to separable filters in the filter bank. However, this approach only provides symmetry around the coordinate axes and rectangular divisions of the frequency spectrum, while in many applications nonrectangular divisions are more desirable and better preserve signal content. Several other approaches, both orthogonal and biorthogonal and using different types of signal lattices, have been proposed in J. Kovacevic and M. Vetterli, "Nonseparable multidimensional perfect reconstruction filter banks and wavelet bases for R.sup.n, " IEEE Trans. Inform. Theory, Vol. 38, No. 2, pp. 533-555, 1992; S. D. Riemenschneider and Z. Shen, "Wavelets and pre-wavelets in low dimensions," J. Approx. Theory, Vol. 71, No. 1, pp. 18-38, 1992; A. Cohen and I. Daubechies, "Non-separable bidimensional wavelet bases," Rev. Mat. Iberoamericana, Vol. 9, No. 1, pp. 51-137, 1993; and A. Cohen and J.-M. Schlenker, "Compactly supported bidimensional wavelet bases with hexagonal symmetry," Constr. Approx., Vol. 9, No. 2, pp. 209-236, 1993. However, these approaches are generally limited to dimensions of two or three, because the algebraic conditions which must be solved to determine filter characteristics become increasingly cumbersome in higher dimensions. Although systematic approaches based on the McClellan transform and cascade structures also exist, these and the other approaches noted above all fail to provide adequate techniques for designing filter banks in arbitrary dimensions.
Recently, a new approach to the study of wavelet construction was provided by the so-called "lifting scheme" as described in W. Sweldens, "The lifting scheme: A custom-design construction of biorthogonal wavelets," Journal of Appl. and Comput. Harmonic Analysis, Vol.3, No.2, pp. 186-200, 1996; and W. Sweldens, "The lifting scheme: A construction of second generation wavelets," &lt;http://cm.bell-labs.com/who/wim&gt;, both of which are incorporated by reference herein. These references show that in one-dimensional, two-channel applications, a filter bank may be designed using two lifting operations, a predict operation and an update operation, where the update filter for implementing the update operation is one half times the adjoint of the predict filter implementing the predict operation. While the original motivation for lifting was to build time-varying perfect reconstruction filter banks or so-called "second generation wavelets," lifting turned out to have several advantages for classic time-invariant wavelet construction. In the time-invariant case, lifting has many connections to earlier approaches. The basic idea behind lifting is that there is a simple relationship between all filter banks that share the same lowpass or the same highpass filter. This relationship was observed in the above-cited M. Vetterli and C. Herley reference, and is sometimes referred to as the Herley-Vetterli lemma. Also, lifting leads to a particular implementation of the filter bank. This implementation is known as a ladder structure, as described in A.A.M.L. Bruekens and A.W.M. van den Enden, "New networks for perfect inversion and perfect reconstruction," IEEE J. Selected Areas Commun., Vol. 10, No. 1, 1992. Recently, it was shown that all finite impulse response (FIR) filter banks fit into the lifting framework. See I. A. Shah and A. A. C. Kalker, "On ladder structures and linear phase conditions for multidimensional biorthogonal filter banks," Preprint, Philips Research Laboratories, Eindhoven, Netherlands, and I. Daubechies and W. Sweldens, "Factoring wavelet and subband transforms into lifting steps," Technical Report, Bell Laboratories, Lucent Technologies, &lt;http://cm.bell-labs.com/who/wim&gt;. Although the above-cited references indicate that the lifting approach is suitable for processing one-dimensional signals in two-channel filter banks, it has not been apparent whether or how lifting could be used for processing signals of arbitrary dimension, and in filter banks with M channels, where M is greater than two. Moreover, the above-cited references are primarily directed to techniques for breaking down an existing filter bank into the lifting framework, and thus fail to provide general techniques for designing a filter which has a desired response while also fitting within the lifting framework.
A need therefore exists for a general approach to building filter banks with any number of channels that may be used to process signals with any number of dimensions.